package com.atguigui.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by  wangjiaxin  on 2021/2/18 5:59 下午
 */
//Java：K 连续位的最小翻转次数
/*
    在仅包含0和1的数组A中，一次K位翻转包括选择一个长度为K的（连续）子数组，同时将子数组中的每个0更改为1，而每个1更改为0。
    返回所需的K位翻转的最小次数，以便数组没有值为0的元素。如果不可能，返回-1。
 */
public class P995MinimumNumberOfKConsecutiveBitFlips {

    public static void main(String[] args) {
        Solution solution = new P995MinimumNumberOfKConsecutiveBitFlips().new Solution();

    }

    class Solution {
        public int minKBitFlips(int[] A, int K) {
            int res = 0;
            Deque<Integer> que = new LinkedList<>();
            for (int i = 0; i < A.length; i++) {
                if (que.size() > 0 && i >= que.peek() + K){
                    que.removeFirst();
                }
                if(que.size() % 2 == A[i]){
                    if (i + K > A.length) return -1;
                    que.add(i);
                    res += 1;
                }
            }
            return res;
        }
    }
}
